

#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <string.h>

typedef struct point {
	double x;
	double y;
} point_t;

static point_t points_src[200];

double point_to_line_distance_calc(const point_t *p1, const point_t *p2, const point_t *p0)
{
	double dy, dx;
	double distance;
	double 	tmp;
	dy = p2->y - p1->y;
	dx = p2->x - p1->x;
	tmp =dy*dy+dx*dx;
	tmp = sqrt(tmp);
	distance = fabs((dy*p0->x)-(dx*p0->y)+p2->x*p1->y-p2->y*p1->x)/tmp;
	return distance;
}

double max_distance_point_get(point_t *points, int n_points, point_t *point, int *index)
{
	point_t p1, p2, p0;
	double distance = 0.0, max_distance=0.0;
	assert(n_points>=3);
	p1 = *points;
	p2 = *(points+n_points-1);
	points++;
	for(int i = 1; i < n_points-1; i++)
	{
		//p0 = *points;
		distance = point_to_line_distance_calc(&p1, &p2, points);
		if(distance > max_distance)
		{
			max_distance = distance;
			*point = *points;
			*index = i;
		}
		points++;
	}
	return max_distance;
}

static int call_times = 0;
static double distance_limit = 0.01;
void point_sample(point_t *points, int n_points)
{
	char ch;
	int index;
	point_t point;
	double distance;
	assert(n_points > 0);
	
	if(n_points >=3) {
		distance = max_distance_point_get(points, n_points, &point, &index); 
		if(distance >= distance_limit){
			point_sample(points, index+1);
        		printf("point x:%f, y:%f, index: %d, call times:%d\n", point.x, point.y, index, ++call_times);
			// ch = getchar();
			// putchar(ch);
			point_sample(points+index, n_points-index);
		} else {
			return;
		}
	  
	} else {
		return;
	}
	     
}

point_t A = {0, 0};
point_t B = {1, 0};
point_t C = {0,1};
int main(int argc, char *argv[])
{
	double distance, max_distance;
	point_t point;
	int index;
	int point_number;
	if(argc != 3)
	{
		printf("argument number is not correct\n");
		return -1;
	}
	sscanf(argv[1], "%d", &point_number);
	sscanf(argv[2], "%lf", &distance_limit);
	printf("points number: %d\n", point_number);
	printf("distance limit %f\n", distance_limit);
	/* 计算距离 */
	distance = point_to_line_distance_calc(&A, &B, &C);
	// printf("%f\n", distance);
	max_distance = max_distance_point_get(points_src, 200, &point, &index);
	point_sample(points_src, point_number);

	// printf("distance %f, x:%f, y:%f, index: %d\n", max_distance, point.x, point.y, index);
	return 0;
}

static point_t points_src[] = {
{320.000000,160.000000},
{319.980062,162.525799},
{319.920254,165.050968},
{319.820591,167.574878},
{319.681097,170.096901},
{319.501806,172.616407},
{319.282765,175.132769},
{319.024027,177.645360},
{318.725657,180.153553},
{318.387730,182.656723},
{318.010328,185.154247},
{317.593548,187.645502},
{317.137491,190.129867},
{316.642273,192.606723},
{316.108016,195.075452},
{315.534854,197.535440},
{314.922929,199.986074},
{314.272394,202.426742},
{313.583411,204.856837},
{312.856152,207.275752},
{312.090798,209.682885},
{311.287540,212.077636},
{310.446578,214.459409},
{309.568121,216.827608},
{308.652389,219.181646},
{307.699610,221.520934},
{306.710021,223.844889},
{305.683868,226.152933},
{304.621408,228.444491},
{303.522905,230.718990},
{302.388634,232.975865},
{301.218876,235.214553},
{300.013924,237.434496},
{298.774077,239.635141},
{297.499644,241.815939},
{296.190944,243.976346},
{294.848303,246.115825},
{293.472054,248.233842},
{292.062541,250.329869},
{290.620115,252.403384},
{289.145137,254.453871},
{287.637972,256.480817},
{286.098998,258.483719},
{284.528596,260.462076},
{282.927160,262.415396},
{281.295088,264.343192},
{279.632787,266.244983},
{277.940670,268.120296},
{276.219160,269.968663},
{274.468686,271.789623},
{272.689684,273.582724},
{270.882597,275.347517},
{269.047876,277.083563},
{267.185979,278.790429},
{265.297368,280.467690},
{263.382514,282.114928},
{261.441896,283.731733},
{259.475996,285.317701},
{257.485305,286.872437},
{255.470318,288.395554},
{253.431538,289.886672},
{251.369473,291.345420},
{249.284637,292.771434},
{247.177549,294.164358},
{245.048735,295.523845},
{242.898725,296.849558},
{240.728055,298.141164},
{238.537265,299.398343},
{236.326903,300.620781},
{234.097518,301.808173},
{231.849666,302.960223},
{229.583908,304.076645},
{227.300809,305.157160},
{225.000936,306.201499},
{222.684864,307.209401},
{220.353170,308.180616},
{218.006434,309.114901},
{215.645242,310.012023},
{213.270182,310.871759},
{210.881846,311.693895},
{208.480829,312.478225},
{206.067729,313.224555},
{203.643149,313.932698},
{201.207692,314.602478},
{198.761965,315.233727},
{196.306577,315.826289},
{193.842142,316.380016},
{191.369272,316.894770},
{188.888584,317.370422},
{186.400697,317.806854},
{183.906230,318.203958},
{181.405805,318.561633},
{178.900045,318.879792},
{176.389575,319.158355},
{173.875021,319.397252},
{171.357008,319.596423},
{168.836165,319.755821},
{166.313120,319.875403},
{163.788501,319.955141},
{161.262939,319.995016},
{158.737061,319.995016},
{156.211499,319.955141},
{153.686880,319.875403},
{151.163835,319.755821},
{148.642992,319.596423},
{146.124979,319.397252},
{143.610425,319.158355},
{141.099955,318.879792},
{138.594195,318.561633},
{136.093770,318.203958},
{133.599303,317.806854},
{131.111416,317.370422},
{128.630728,316.894770},
{126.157858,316.380016},
{123.693423,315.826289},
{121.238035,315.233727},
{118.792308,314.602478},
{116.356851,313.932698},
{113.932271,313.224555},
{111.519171,312.478225},
{109.118154,311.693895},
{106.729818,310.871759},
{104.354758,310.012023},
{101.993566,309.114901},
{99.646830,308.180616},
{97.315136,307.209401},
{94.999064,306.201499},
{92.699191,305.157160},
{90.416092,304.076645},
{88.150334,302.960223},
{85.902482,301.808173},
{83.673097,300.620781},
{81.462735,299.398343},
{79.271945,298.141164},
{77.101275,296.849558},
{74.951265,295.523845},
{72.822451,294.164358},
{70.715363,292.771434},
{68.630527,291.345420},
{66.568462,289.886672},
{64.529682,288.395554},
{62.514695,286.872437},
{60.524004,285.317701},
{58.558104,283.731733},
{56.617486,282.114928},
{54.702632,280.467690},
{52.814021,278.790429},
{50.952124,277.083563},
{49.117403,275.347517},
{47.310316,273.582724},
{45.531314,271.789623},
{43.780840,269.968663},
{42.059330,268.120296},
{40.367213,266.244983},
{38.704912,264.343192},
{37.072840,262.415396},
{35.471404,260.462076},
{33.901002,258.483719},
{32.362028,256.480817},
{30.854863,254.453871},
{29.379885,252.403384},
{27.937459,250.329869},
{26.527946,248.233842},
{25.151697,246.115825},
{23.809056,243.976346},
{22.500356,241.815939},
{21.225923,239.635141},
{19.986076,237.434496},
{18.781124,235.214553},
{17.611366,232.975865},
{16.477095,230.718990},
{15.378592,228.444491},
{14.316132,226.152933},
{13.289979,223.844889},
{12.300390,221.520934},
{11.347611,219.181646},
{10.431879,216.827608},
{9.553422,214.459409},
{8.712460,212.077636},
{7.909202,209.682885},
{7.143848,207.275752},
{6.416589,204.856837},
{5.727606,202.426742},
{5.077071,199.986074},
{4.465146,197.535440},
{3.891984,195.075452},
{3.357727,192.606723},
{2.862509,190.129867},
{2.406452,187.645502},
{1.989672,185.154247},
{1.612270,182.656723},
{1.274343,180.153553},
{0.975973,177.645360},
{0.717235,175.132769},
{0.498194,172.616407},
{0.318903,170.096901},
{0.179409,167.574878},
{0.079746,165.050968},
{0.019938,162.525799},
{0.000000,160.000000},
};



